#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
using namespace std;
struct cmp
{
    bool operator()(const int& a, const int& b)
    {
        return a > b;
    }


};


bool compare(int& a, int& b){
    return a > b;
}

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }
    void addNum(int num) {
        if(m_less.size() == 0)
        {
            m_less.push(num);
            return;
        }
        if(num > m_less.top())
            m_greater.push(num);
        else m_less.push(num);
        int l_size = m_less.size();
        int g_size = m_greater.size();
        if((m_less.size() - m_greater.size()) > 1){
//        if((l_size - g_size) > 1){
            int temp = m_less.top();
            m_less.pop();
            m_greater.push(temp);
        }
        else if((m_greater.size() - m_less.size() ) > 1){
            int temp = m_greater.top();
            m_greater.pop();
            m_less.push(temp);
        }
        return;
    }

    double findMedian() {
        int temp1 = m_less.top();
        int temp2 = m_greater.top();
        if( m_less.size() == m_greater.size() )
            return ((double)temp1 + (double)temp2 ) / 2;
        if( m_less.size() > m_greater.size() )
            return m_less.top();
        else return m_greater.top();
    }
private:
    priority_queue<int> m_less;
    priority_queue<int, vector<int>, greater<> > m_greater;
};

int main() {
    bool signal = (-1 > 1);

    priority_queue<int, vector<int>, greater<>> p_que;
    p_que.push(5);
    p_que.push(4);
    p_que.push(6);
    set<int, greater<>> m_set;
    m_set.insert(4);
    m_set.insert(6);
    m_set.insert(5);
    while(!p_que.empty()){
        std::cout<<p_que.top()<<endl;
        p_que.pop();
    }
    for(auto s : m_set){
        std::cout<<s<<endl;
    }
    MedianFinder med;
    med.addNum(1);
    med.addNum(2);
    med.addNum(3);
    double m = med.findMedian();
    cout<<m<<endl;
    return 0;
}
